package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/partition-list">分隔链表(Partition List)</a>
 * <p>给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 <b>小于</b> x 的节点都出现在 <b>大于或等于</b> x 的节点之前。</p>
 * <p>你应当 <b>保留</b> 两个分区中每个节点的初始相对位置。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,4,3,2,5,2], x = 3
 *      输出：[1,2,2,4,3,5]
 *
 * 示例 2：
 *      输入：head = [2,1], x = 2
 *      输出：[1,2]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *      <li>链表中节点的数目在范围 [0, 200] 内</li>
 *      <li>-100 <= Node.val <= 100</li>
 *      <li>-200 <= x <= 200</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/4/27 11:49
 */
public class LC0086PartitionList_M {
    static class Solution {
        public ListNode partition(ListNode head, int x) {
            // 如果链表中无节点。或者有一个节点，直接返回
            // 节点值范围：[-100,100]，x值范围：[-200,200]。x<=-100或x>=100直接返回
            if (head == null || head.next == null || x <= -100 || x >= 100) {
                return head;
            }
            ListNode leListHeadNode = new ListNode();
            ListNode leListCurrNode = leListHeadNode;

            ListNode geListHeadNode = new ListNode();
            ListNode geListCurrNode = geListHeadNode;
            ListNode currNode = head;
            while (currNode != null) {
                if (currNode.val < x) {
                    leListCurrNode.next = currNode;
                    leListCurrNode = leListCurrNode.next;
                } else {
                    geListCurrNode.next = currNode;
                    geListCurrNode = geListCurrNode.next;
                }
                currNode = currNode.next;
            }
            geListCurrNode.next = null;
            leListCurrNode.next = geListHeadNode.next;
            return leListHeadNode.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.partition(Generator.create(2, 1), 2));
        Printer.printListNode(solution.partition(Generator.create(1, 4, 3, 2, 5, 2), 3));
    }
}